package linkedlist

import "fmt"

type ListNode struct {
	Value int
	Next  *ListNode
}

type LinkedList struct {
	Head *ListNode
}

func TestCycleLinkedList() {
	l := LinkedList{}
	l.initCycleLinkedList()
	node, size := l.getJoinNode()
	fmt.Printf("node:%d,size:%d", node.Value, size)
}

func (l *LinkedList) initCycleLinkedList() {
	l.Head = &ListNode{0, nil}
	node1 := &ListNode{1, nil}
	node2 := &ListNode{2, nil}
	node3 := &ListNode{3, nil}
	node4 := &ListNode{4, nil}
	node5 := &ListNode{5, nil}
	node6 := &ListNode{6, nil}
	node7 := &ListNode{7, nil}
	node8 := &ListNode{8, nil}
	node9 := &ListNode{9, nil}
	l.Head.Next = node1
	node1.Next = node2
	node2.Next = node3
	node3.Next = node4
	node4.Next = node5
	node5.Next = node6
	node6.Next = node7
	node7.Next = node8
	node8.Next = node9
	node9.Next = node6
}

func (l LinkedList) getJoinNode() (*ListNode, int) {
	ringSize := 0
	fast, slow := l.Head, l.Head
	var firstJoin *ListNode
	for fast != nil {
		slow = slow.Next
		fast = fast.Next
		if fast == nil {
			break
		}
		fast = fast.Next
		if fast == slow {
			firstJoin = fast
			break
		}
	}
	if firstJoin == nil {
		return firstJoin, ringSize
	}
	pre, pos := l.Head, firstJoin
	for pre != pos {
		pre = pre.Next
		pos = pos.Next
	}
	node := firstJoin.Next
	ringSize = 1
	for node != firstJoin {
		node = node.Next
		ringSize++
	}
	return pre, ringSize
}

func (l LinkedList) reverseLink() *ListNode {
	head := l.Head
	var pre *ListNode
	for head != nil {
		next := head.Next
		head.Next = pre
		pre = head
		head = next
	}

	return nil
}
